package oj;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 郝文雪
 * @date 2022/8/28 16:36
 * @Description Test
 */
public class LC84 {
    public int largestRectangleArea(int[] heights) {
        // 单调栈+哨兵
        int len=heights.length;
        if(len==0){
            return 0;
        }
        if(len==1){
            return heights[0];
        }
        int res=0;
        Deque<Integer> d=new ArrayDeque<>(len);
        int[] newHeights=new int[len+2];
        for(int i=1;i<len+1;i++){
            newHeights[i]=heights[i-1];
        }
        for(int i=0;i<len+2;i++){
            while(!d.isEmpty()&&newHeights[i]<newHeights[d.peekLast()]){
                int curHeight=newHeights[d.pollLast()];
                int curWidth=i-d.peekLast()-1;
                res=Math.max(res,curWidth*curHeight);
            }
            d.addLast(i);
        }
        return res;

        //单调栈，无哨兵做法
//        int len=heights.length;
//        if(len==0){
//            return 0;
//        }
//        if(len==1){
//            return heights[0];
//        }
//        int res=0;
//        Deque<Integer> d=new ArrayDeque<>(len);
//        for(int i=0;i<len;i++){
//            while(!d.isEmpty() && heights[i]<heights[d.peekLast()]){
//                int curHeight=heights[d.pollLast()];
//                int curWidth;
//                if(d.isEmpty()){
//                    curWidth=i;
//                }else{
//                    curWidth=i-d.peekLast()-1;
//                }
//                res=Math.max(res,curWidth*curHeight);
//            }
//            d.addLast(i);
//        }
//        while(!d.isEmpty()){
//            int curHeight=heights[d.pollLast()];
//            int curWidth;
//            if(d.isEmpty()){
//                curWidth=len;
//            }else{
//                curWidth=len-d.peekLast()-1;
//            }
//            res=Math.max(res,curWidth*curHeight);
//        }
//
//        return res;
    }
}
